package top.carrotguo.sorting;

import top.carrotguo.bean.linklist.IntLinkList;
import top.carrotguo.bean.linklist.LinkNode;

/**
 * 选择排序
 * 复杂度：O(n^2) 弱于插入排序
 * @Author: Carrot
 * @Mail: 1053155183carrot@gmail.com
 * @Date: Created in 19:15 2018-05-29
 */
public class SelectionSort {
    /**
     * linkNode的n个后继中查找最大结点并且返回
     * @param p 查找开始位置
     * @param n 查找的个数范围
     * @return
     */
    public LinkNode<Integer> searchMax(LinkNode<Integer> p, int n){
        LinkNode<Integer> maxNode = p;
        while (0<n--) {
            if (maxNode.value<p.value) {
                maxNode = p;
            }
            p = p.nextNode;
        }
        return maxNode;
    }

    /**
     * 选择排序（选择最大的放到尾部）
     * @param p 排序开始位置
     * @param n 排序的元素个数
     */
    public void selectionSort(IntLinkList linkList, LinkNode<Integer> p, int n){
        //待排序区间(head,tail)
        LinkNode head = p.preNode;
        LinkNode tail = p;
        //tail指向链表尾
        for (int i=0; i<n; i++) {
            tail = tail.nextNode;
        }
        while (1<n) {
            linkList.insertBefore(linkList.remove(searchMax(head.nextNode,n)),tail);
            //尾部向前移动一位  因为最后一位已经是筛选出来最大的
            tail = tail.preNode;
            n--;
        }
    }

    public static void main(String[] args){
        IntLinkList linkList = new IntLinkList();
        linkList.insertLast(3);
        linkList.insertLast(2);
        linkList.insertLast(6);
        linkList.insertLast(8);
        linkList.insertLast(34);
        linkList.insertLast(31);
        linkList.selectionSort(linkList.head.nextNode,linkList.size);
        linkList.printList();
    }
}
